import java.util.SortedMap;

/**
 * @Created by liutl
 * @date 2018/4/25 20:52
 */
public class QuickSort {

    private QuickSort() {
    }

    //对arr[l...r]部分进行partition操作
    private static int partition(Comparable[] arr, int l, int r) {
        Comparable v = arr[l];

        int j = l;//arr[l+1....p-1] <v ;arr[j+1...r]>arr[p]
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(v) < 0) {
                j++;
                swap(arr, j, i);
            }

        }
        swap(arr, l, j);
        return j;
    }

    //地柜使用快速排序，对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr,l,p-1);
        sort(arr,p+1,r);
    }
    public static void sort(Comparable[] arr){
        int n=arr.length;
        sort(arr,0,n-1);
    }

    public static void swap(Object[] arr, int j, int i) {
        Object t = arr[i];
        arr[j] = arr[i];
        arr[i] = t;
    }

    public static void main(String[] args) {
        int N = 1000000;

    }

}
